1. Field of the Invention
The present invention relates to the field of multi-objective optimization methods, and especially to methods of solving large-scale design optimization tasks.
2. Description of the Prior Art
Optimization methods started with Newton's method, which was described by Isaac Newton in “De Analysi Per Aequationes Numero Terminorum Infinitas,” written in 1669. Since then a lot of methods for optimization of functions have been developed and applied for solving a variety of technical and scientific problems. Modern applied mathematics includes a large collection of optimization methods created over three centuries. An important group of such methods is based on using 1st and 2nd order derivatives of objective function [5, 6, 7] (Newton-Ralphson, Steepest descent, Conjugate gradient, Sequential quadratic programming, et cetera).
Italian economist Vilfredo Pareto introduced the concept of Pareto optimality in 1906 (see related definitions and multi-objective optimization problem formulation in p.A.1.) The concept has broad applications in economics and engineering. The Pareto optimality concept became the starting point for a new discipline of multi-objective optimization, which is intended to find trade-offs for several contradicting objectives. For instance, survivability and cost are contradicting objectives in ship design. If survivability is improved then cost may become too high. If the cost is decreased then survivability may become worse. It is important to find a reasonable trade-off for these two objectives, which determines the practical value of the multi-objective optimization concept.
The general multi-objective optimization problem is posed as follows [1]:MinimizeX: F(X)=[F1(X),F2(X), . . . ,Fm(X)]T  (1)subject: qj(X)≦0; j=1,2, . . . k
Here is a particular sample of a small optimization task with two independent variables and two objective functions:Minimize: F1=1−exp[−(x1−1/√{square root over (2)})2−(x2−1/√{square root over (2)})2];  (2)Minimize: F2=1−exp[−(x1−1/√{square root over (2)})2−(x2−1/√{square root over (2)})2];−4≦x1,x2≦4;
Dimension of multi-objective optimization tasks can be very different from two-dimensional tasks like the task (2) to large-scale tasks with dozens of objective functions and thousands of independent variables typical for aerospace, automotive industries, ship design, et cetera. Today it is impossible to design an airplane, automobile, or ship without intensive use of multi-objective optimization algorithms. This determines market demand and practical value of efficient multi-objective optimization algorithms.
There are no numerical methods developed for solving multi-objective optimization tasks. So, first attempts to solve such tasks were based on using well developed for the moment gradient-based optimization methods. In order to use those single-objective methods for multi-objective optimization a scalarization technique has been developed, which allowed substitution of multiple objective functions by a weighted exponential sum of those functions. The following is the simplest and the most common form of scalarization for the optimization problem (3):
                              U          =                                    ∑                              i                =                1                            m                        ⁢                                                            w                  i                                ⁡                                  [                                                            F                      i                                        ⁡                                          (                      x                      )                                                        ]                                            p                                      ;                                            F              i                        ⁡                          (              x              )                                >          0                ;                  ∀          i                                    (        3        )            
In the early 1970's John Holland invented Genetic Algorithms (GAs). A genetic algorithm is a heuristic used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to optimization theory and other fields of computer science. Genetic algorithms use biologically derived techniques such as inheritance, mutation, natural selection, and crossover. GAs differs from conventional optimization algorithms in several fundamental respects. They do not use derivative or gradient information, but instead rely on the observed performance of evaluated solutions, and the transition rules are probabilistic rather than deterministic.
Thus, there are two groups of known multi-objective optimization methods: scalarization methods and multi-objective genetic algorithms.
1. Scalarization methods use a global criterion to combine multiple objective functions mathematically. These methods require solving a sequence of single-objective problems. The most common method of the group is weighted sum method. The method has several serious problems:
a. Use of gradients for determination of direction for the next step works perfectly when a single objective function is optimized. But utilizing the same technique for a weighted sum of multiple objective functions does not allow controlling values of individual objective functions during the optimization process. It creates serious problems finding evenly distributed Pareto optimal points:                It is impossible to obtain points on non-convex portions of the Pareto optimal set in the objective function space [1]. This is important because the best trade-off solution can be lost there. See FIG. 1a with Pareto-optimal points found by a gradient-based method for a task with non-convex Pareto frontier. All found Pareto points are concentrated in the areas of best and worse objective functions' values. Non-convex part of the Pareto frontier is empty;        Uniform distribution of Pareto optimal points cannot be guaranteed even if the weights are varying consistently and continuously. It means that Pareto set will be incomplete and inaccurate [2]. This leads to the situation when the best optimal design solution is missed;        
b. Methods are based upon usage of a priori articulation of preferences for determining weights in the weighted sum. However, a satisfactory a priori selection of weights does not necessarily guarantee that the final solution will be acceptable;
c. Mixed discrete and continuous problems cannot be solved by derivative based optimization methods. Any real life design problem naturally has discrete or integer design parameters. Substitution of discrete parameters by continuous ones compromises accuracy of the optimization result significantly.
2. Multi-objective Genetic Algorithms combine the use of random numbers and information from previous iterations to evaluate and improve a population of points rather than a single point at a time. GAs are based on heuristic strategies not related to the nature of multi-objective optimization. As a result, GAs are:
a. Computationally extremely intensive and resource consuming;
b. Do not provide adequate accuracy. See FIG. 1c with Pareto-optimal points found by one of Genetic Algorithms. The algorithm was not able to find points located closer to the true solution, which is the diagonal of the x1-x2 diagram;
c. Do not provide an objective measure to evaluate divergence of found solutions from true Pareto frontier;
d. The objective of GAs is to find the optimal solution to a problem. However, because GAs are heuristics, the solution found is not always guaranteed to be the optimal solution. See a sample on FIG. 1c. 
Traditional gradient-based optimization methods are designed to solve single-objective optimization tasks. Absence of numerical methods designed specifically for multi-objective optimization, forced engineers to invent an artificial scalarization technique, which allows considering multi-objective optimization tasks as single-objective ones, and using gradient-based methods.
For the same reason, engineers started utilizing heuristic GAs for multi-objective optimization. Both approaches are not designed to solve multi-objective optimization tasks and do not have appropriate mathematical foundation, and as result have above listed disadvantages.
Our invention offers new a type of numerical analysis specifically targeted to solve multi-objective optimization tasks. It is based on mathematically proven results (see Appendix A) and intended to overcome disadvantages of existent approaches.
1. Andersson J., “A Survey of Multi-objective Optimization in Engineering Design,” Fluid and Mechanical Engineering Systems, Linköping University, Sweden, LiTH-IKP-R1097.
2. Marler, R. T., and Arora, J. S. (2004), “Survey of Multi-objective Optimization Methods for Engineering”, Structural and Multidisciplinary Optimization, 26, 6, 369-395.
3. Pareto, V. 1906: Manuale di Economica Politica, Societa Editrice Libraria. Milan; translated into English by A. S. Schwier as Manual of Political Economy. Edited by A. S. Schwier and A. N. Page, 1971. New York: A. M. Kelley.
4. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press: Ann Arbor, Mich.
5. Vanderplaats, G. N., Numerical Optimization Techniques for Engineering Design, McGraw-Hill Book Co., 1984.
6. Haftka, R. T., and Gurdal, Z., Elements of Structural Optimization, Kluwer Academic Publishers, 1992.
7. Walsh, G. R., Methods of Optimization, John Wiley, 1975.